package leetcode_题库;

import java.util.*;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/23 14:07 星期二
 */
public class _73_矩阵置零 {
    public static void main(String[] args) {
        int[][] matrix = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
//        setZeroes(matrix);
        setZeroes2(matrix);
        System.err.println(Arrays.deepToString(matrix));
    }

    /**
     * 官解：第二种，非最优解，但较好理解且差异不大
     * > 2022/08/23 15:22:36
     * 解答成功:
     * 	执行耗时:0 ms,击败了100.00% 的Java用户
     * 	内存消耗:42.7 MB,击败了89.33% 的Java用户
     * @param matrix
     */
    private static void setZeroes2(int[][] matrix) {
        //这种算法优异之处在于，我们取原数组的第一行和第一列为标记，节省空间。
        //但在赋值后，会覆盖原本的值，无门无法判断原本第一行和第一列中是否有0
        //所以，引入两变量进行记录，第一行和第一列中是否有0
        boolean flagRow = false, flagCol = false;
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                //在列上存在为0的元素
                flagCol = true;
            }
        }
        for (int i = 0; i < matrix[0].length; i++) {
            if (matrix[0][i] == 0) {
                //在行上存在为0的元素
                flagRow = true;
            }
        }
        //然后，从下标为1开始，如果第i，j中存在0，就让其对应的第一行和第一列映射位置修改为0
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = matrix[i][0] = 0;
                }
            }
        }
        //根据第一行和第一列的标记，把行或列为0的元素修改为0
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0){
                    matrix[i][j] = 0;
                }
            }
        }

        //我们得把第一行和第一列，这俩标记数组处理一下了，如果第一行中有0，全改为0，如果第一列中有0，全改为0
        if (flagCol){
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
        if (flagRow){
            for (int i = 0; i < matrix[0].length; i++) {
                matrix[0][i] = 0;
            }
        }

    }

    /**
     * 自己写的勾吧算法
     * > 2022/08/23 14:33:32
     * 解答成功:
     * 执行耗时:4 ms,击败了12.10% 的Java用户
     * 内存消耗:42.9 MB,击败了58.13% 的Java用户
     *
     * @param matrix
     */
    public static void setZeroes(int[][] matrix) {
        //存坐标
        Map<Integer, Set<Integer>> map = new HashMap<>(matrix.length * matrix[0].length);
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] != 0) {
                    continue;
                }
                Set<Integer> set = map.get(i) != null ? map.get(i) : new HashSet<>();
                set.add(j);
                map.put(i, set);
            }
        }
        //操作置零
        map.forEach((k, v) -> {
            v.forEach(vSon -> {
                setZeroes(matrix, k, vSon);
            });
        });
    }

    public static void setZeroes(int[][] matrix, int i, int j) {
        for (int x = 0; x < matrix.length; x++) {
            matrix[x][j] = 0;
        }
        for (int y = 0; y < matrix[0].length; y++) {
            matrix[i][y] = 0;
        }
    }
}
